This invention relates to techniques for determining location and, specifically, to techniques that utilize satellite-based Global Positioning Systems (GPS) or Global Navigational Satellite Systems (GNSS).
Satellite-based positioning systems (SPSs), including the NAVSTAR Global Positioning System (GPS), developed by the United States Department of Defense, as well as the GLONASS and Galileo GPS systems, use a constellation of satellites that transmit precise microwave signals, which allows the SPS receivers to determine their current location. Initial applications were predominantly military; the first widespread consumer application was navigational assistance.
With the explosive growth in mobile communications devices, a new wave of location-based applications is emerging. These applications are characterized by a requirement for device-centered maps. One example is a form of “Yellow Pages” in which a map centered at the location of the mobile device presents user-selected establishments (e.g., barber shops) in situ. Another example would be an application enabling one to locate, on a device-centered map, members of his or her social network. Unlike navigational assistance, these emerging applications running on mobile devices are often intended to be used weak-signal environments such as inside buildings or in “urban canyons” in which the received satellites signal are too weak to provide a position fix.
For example, conventional GPS receivers are unable to obtain location coordinates in indoor and urban canyon locations, especially in cold start operation. To get a position fix, a GPS receiver requires navigational data for the satellites. This navigational data includes the ephemeris data for each visible satellite (which includes its position in space as well as its speed). Traditionally, this navigational data is modulated onto the GPS signal itself (it is commonly called the “nav bits”). But this navigational data transmission is very low bandwidth (e.g., 50 bits/second). Should a GPS receiver be powered up in a “cold start” in which it has no (or incomplete) knowledge of its location and the visible satellites, the acquisition of the required navigational data can take up to 15 minutes. But GPS technology is now commonplace in cellular telephones, which provides a shortcut. The base station can transmit all the “nav bits” to the handset. Such assistance goes by a number of names such as “extended ephemeris.” In this fashion, a handset can immediately know which satellites are visible and what their ephemeris is. Extended ephemeris thus markedly reduces the time to first fix (TTTF). But even with extended ephemeris, the GPS receiver must still acquire the satellite signals. Extended ephemeris does nothing about boosting unacceptably weak GPS signals in indoor and urban canyon locations. There is thus a need in the art for systems and techniques that solve the problem of acquiring SPS signals in weak-signal environments. This need in the art is exacerbated by the explosive growth of location-based social media and other applications that are often used indoors or in other weak-signal environments.
To better understand the problems of faced by SPS receivers in weak-signal environments, a brief tutorial will be provided. In particular, the operation of a NAVSTAR GPS receiver will be discussed. But it will be appreciated that the concepts and principles disclosed herein are widely applicable to other types of SPS receives. Each GPS satellite transmits signals containing its unique identity, its three-dimensional coordinates, and the time stamp of when the signal was sent. Each satellite also transmits data pertaining to the location of the other satellites in the constellation, commonly referred to as almanac data, which are utilized by navigation equations. FIG. 1a is an illustration of the data structure of the signal broadcast by each satellite, which is a phase-modulated carrier. The phase-modulation includes a coarse acquisition (C/A) code. Each satellite has its own unique C/A code, which is a binary code 1023 bits long. Each bit in the C/A code sequence is typically denoted as a “chip” since it does not represent data. The chips are transmitted at a 1.023 MHz rate such that each C/A code sequence has a period of 1 millisecond (ms). The C/A code is a pseudo random number (PRN), which looks like a random code but is clearly defined for each satellite.
In addition to the C/A code, the transmitted signal includes the 50 Hz navigational signal overlay that provides the location of each satellite, clock corrections, and other system parameters. The 50 Hz signal is often referred to as the GPS navigation message. As shown in FIG. 1a, a navigational bit is a phase overlay on twenty consecutive C/A codes. At the navigation bit boundary, the phase overlay either flips (going from +1 to −1 or from −1 to +1) or stays the same. As will be discussed further herein, such a phase transition is problematic with regard to coherently integrating or summing the cross-correlations for a series of PRN sequences that extends over the navigation bit boundaries. For example, if one navigation bit is +1 and the subsequent navigation bit is −1, the coherent integration of the cross-correlations for the PRN sequences for the first navigation bit is opposed by the coherent integration over the subsequent navigation bit. The GPS navigation message, in combination with the acquired pseudo ranging information from the C/A codes, is used to complete the navigation equations, which determine the location coordinates of the GPS receiver. The navigation bits themselves are is divided into 25 frames, each having a length of 1500 bits (meaning an interval of 30 seconds for transmission). FIG. 1b illustrates a frame of the complete signal.
To obtain a “pseudorange” to a given satellite, a GPS receiver correlates a copy of a satellite's unique PRN sequence with the received PRN sequence. The copy is correlated with regard to each chip position. In other words, prior to acquiring the satellite signal, an SPS receiver does not know which chip position corresponds to the arrival time for the received PRN sequence. The pseudo-random nature of PRN sequence is quite advantageous in that received noise is effectively de-correlated by such a code. But if the copy of the PRN sequence is properly aligned with the received PRN sequence in a cross-correlation, all the chips coherently add together. But the noise cannot coherently add. The received signal is then “pulled” out of the noise by the gain of all the chips adding together. This correlation peak occurs for one of the possible chip alignments of the received PRN sequence with the replica PRN sequence. The received PRN sequence is then located in time—its arrival time is known. But an SPS receiver must also search in frequency as well due to Doppler shift and local oscillator (LO) uncertainties. Once the received PRN sequence is located in time and frequency, the SPS receiver can obtain a “pseudorange” between it and the transmitting satellite. This pseudorange is based upon the time the satellite transmitted the PRN sequence and the time of reception by the SPS receiver. Based upon this elapsed time and the fact that the satellite transmission occurred at the speed of light, the SPS receiver can calculate the range between it and the transmitting satellite. But note that the satellite has a very accurate atomic clock. So there is relatively little uncertainty to the reported transmission time by the satellite. In contrast, the SPS receiver will typically have a relatively inexpensive clock, which is substantially less accurate than the satellite clock. The SPS receiver clock thus has an unknown offset to the satellite clock. For this reason, the time the SPS receiver believes it received the PRN sequence is not the ‘true” time that it would have calculated if it had a more accurate clock that matched the time clocked by the expensive satellite clock. This unknown clock offset adds uncertainty to the range measurement, hence it is denoted as a pseudorange.
Referring now to FIG. 2a, an SPS receiver knows the transmitting satellite's position from the associated ephemeris (whether that ephemeris was taken from the nav bits or was received in an extended ephemeris scheme). For example, the position of a satellite A 11 and a satellite B 12 is known. A pseudorange A 13 from satellite A forms a sphere about the satellite's position. If the SPS receiver were not earth-bound, it could be anywhere on the sphere. But if we assume that the SPS receiver is on the earth's surface, the pseudorange defined sphere intersects the earth's surface in a circular fashion as shown in FIG. 2a. A similar pseudorange-defined sphere about satellite B with regard to its pseudorange 14 produces another circular intersection. Since the SPS receiver is on the earth's surface (or if we assume so), it will then be located at the resulting intersection points 15 and 16, resulting in an ambiguous location. An SPS receiver thus needs more than just a pair of pseudoranges to get a position fix.
The clock offset uncertainty that affects location determination may be better understood with reference to FIG. 2b, which illustrates the result of the two acquired satellites SAT A 11 and SAT B 12 when the clock in SPS receiver 10 is 2 milliseconds late as compared to the clock of the SPS satellites. This causes the travel-time of the transmitted signals to appear to be 2 milliseconds longer than it actually is. The dotted ovals represent the actual range, Range_A 13 and Range_B 14, whereas the pseudoranges include this 2 ms clock offset. As the transmitted signals travel at the speed of light, even a small clock offset translates into large inaccuracies. Since atomic clocks are not a practical solution for SPS receivers, the problem is solved using an additional pseudorange.
FIG. 2c illustrate the intersections of a third pseudorange 22 with respect to a satellite C 21 with the pseudoranges from FIG. 2b. The pseudoranges all have the same clock offset because they are based they are based upon the same reception times in one SPS receiver. The three intersection points resulting from the three pseudoranges intersect at point 19, point 23 and point 24. From the intersection points, the clock offset is calculated by adjusting the clock offset until the three intersection points merge to a single point. Once this is completed, the clock of the SPS receiver has been synchronized with the atomic clock of the SPS satellite system. This is a 2-dimensional location as this point represents the intersection of the adjusted pseudoranges on the surface of the Earth. Additionally, acquiring a fourth concurrent satellite, resulting in a fourth concurrent pseudorange, will allow for a 3-dimensional location coordinate to be determined. Our attention now will switch to the process by which pseudoranges from individual satellites in the constellation are acquired, as it represents the most challenging aspect of obtaining the location coordinates of a GPS receiver. As described above, each SPS satellite broadcasts its unique identity via its particular PRN sequence (e.g., GPS uses a C/A code). The PRN sequence for each satellite is known by the SPS receiver, which compares it with the received composite signal. FIG. 3 shows a block diagram of a conventional SPS receiver. The composite signal from the SPS satellite constellation 30 is received by the RF front end 25, which down-converts the RF signal and converts it to a digital signal stream. The digital signal stream is input to the correlator block 26. Correlator block 26 correlates the incoming digital signal with the PRN sequence replica 29 stored in memory for each SPS satellite.
FIG. 4 illustrates how correlator 26 determines the receive or arrival time of the signal from an SPS satellite by using the well-understood process of cross correlation. Even with a clear view of the sky, received signals are weak and all satellites broadcast over the same carrier frequency. Most SPS receivers implement multiple correlator blocks in parallel in order to acquire pseudoranges from multiple satellites simultaneously. For the purpose of this discussion, we will focus on the operation of a single correlator block. The composite digital signal that is received by the SPS receiver is input to a delay line made up of multiple delay elements. Corresponding chips (unit of the spreading code) from a PRN sequence replica 29 for the specific satellite that is being acquired are multiplied with the output of each delay element. The product of each delayed signal and chips from the PRN sequence replica 29 are summed and processed in a coordinate generator 28.
FIGS. 5 and 6 illustrates the correlator output of correlator 26 for different received signal powers. In FIG. 5, the received PRN sequence strength or SNR was such that correlator peaks representing the chip corresponding to the arrival time are greater than the noise floor, including peaks representing both white Gaussian noise as well as transmitted signal from a SPS satellite going through a multipath channel. This allows for the successful acquisition of the satellite. The received signal advances through the correlator delay line elements a chip at a time at the chip rate (1.023 MHz). The received PRN sequence will thus only align with the replica PRN sequence every n chips, where n is the number of chips in a complete PRN sequence. For example, n is 1023 in a GPS system such that the PRN sequence period is a millisecond. If the received signal is sufficiently powerful (it can actually be quite weak due to the power of coherently adding 1023 chips), a correlation peak occurs as shown in FIG. 5 that will repeat every 1 ms. This peak corresponds to the arrival time of a complete C/A code from the transmitting satellite, albeit with the clock offset uncertainty. The corresponding transmission time of the GPS signal is determined based on the time-stamp of the transmitted signal to determine the transmission delay, which is then converted according to the speed of light into a pseudorange in coordinate generator 28. When this information is acquired from four or more concurrent satellites, coordinate generator 28 employs the resulting navigational equations to determine the location coordinates of a GPS receiver (or three acquired concurrent satellites for a two-dimensional coordinate).
In practice, the process of cross correlation is much more involved. For example, movement of an SPS receiver relative to the individual satellites causes Doppler shifts. But more significantly, especially when the GPS receiver is located in a weak-signal environment such as indoor or urban canyon locations, path losses and signal multi-path significantly reduce the signal-to-noise ratio of the received signal, limiting the ability to successfully determine the signal travel-time distance and thus any ranging information between the satellite and the GPS receiver. In other words, the cross-correlation process would not yield any discernable peaks. FIG. 6 illustrates the correlator output in such a weak-signal environment. In this case, the correlator peaks are not distinguishable because they do not rise above the noise floor. Because the correlator peaks cannot be identified, it is not possible to determine the travel time necessary to determine the pseudorange information. There can be no position fix in such a weak-signal environment unless further processing is involved as discussed herein.
It is well known that increasing the signal-to-noise ratio via processing gain, and thus improving the ability to acquire the transmitted signals, can be achieved by coherently adding the cross-correlations for a series of PRN sequences. However, in practice, there are many significant technical challenges to increasing the processing gain and receive sensitivity by increasing the processing time. The gain from such coherent integration in conventional SPS receivers saturates at well under twenty PRN sequences (20 milliseconds in a GPS system). This explains the poor indoor and urban-canyon performance of current SPS receivers. There are a number of reasons that limit the coherent correlation times. First, as discussed above, the navigation data overlay such as the 50 Hz data overlay in a GPS system creates a structural boundary at every navigation symbol boundary (every 20-millisecond interval for GPS). As also mentioned earlier, the local clock used in SPS receivers is relatively inaccurate. When correlation times are increased, the clock drift during the length of the correlation period is large enough to degrade processing gain. In addition, all SPS satellite transmissions have a Doppler shift that depends upon their particular location in space relative to the SPS receiver. Moreover, if the SPS receiver is not stationary, its own motion compounds the satellite-motion-induced Doppler shift on the received satellite transmission. Another significant barrier is that SPS receivers are subject to low frequency fading, especially in indoor and urban-canyon locations. Low frequency fading refers to the variation of received signal strength from each satellite in the order of less than 10 Hz. This is due to the variation of signal blockers in line of sight of each of the satellites in the constellation. Movement of people and equipment also contribute to the variation of fading characteristics for each satellite signal. The signal fading significantly lowers the probability of the signals being acquired from a sufficient number of concurrent satellites to determine a position fix. Given these issues, the channel de-correlates both spatially and temporally.
A prior art example of an attempt to extend processing time beyond the navigation data symbol boundary such as the 50 Hz overlay boundary in GPS is Krasner (U.S. Pat. No. 6,016,119). FIG. 6 illustrates a block diagram depiction of aspects described by Krasner. Multiple correlator blocks are employed to process signals spanning multiple 50 Hz overlay boundaries. In order to account for the unknown values of the 50 Hz overlay signal, the output from each correlator block is squared, removing the sign. The squaring function removes the 50 Hz phase information, resulting in incoherent processing and significantly limiting the processing gain. As a consequence, this technique is not currently being practiced in commercially available products.
Accordingly, there is a need in the art for improved satellite-based position system (SPS) signal processing techniques for weak-signal environments.